package 反转链表II92;


/**
 * @author 谢阳
 * @version 1.8.0_131
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left >= right) {
            return head;
        }
        ListNode temp = head;
        ListNode leftNode = null;
        ListNode rightNode = null;

        int count = 1;
        while (temp!= null){
            if (count == left) {
                leftNode = temp;
            }

            if (count == right) {
                rightNode = temp;
                break;
            }

            temp = temp.next;
            count++;
        }
        swap(leftNode,rightNode);

        reverseBetween(leftNode,2,right - left);

        return head;

    }

    public void swap (ListNode node1,ListNode node2) {
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }

    public ListNode reverseBetween2(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        ListNode temp = new ListNode(0);
        temp.next = head;

        ListNode beforeLeft = temp;
        for (int i = 0; i < left - 1; i++) {
            beforeLeft = beforeLeft.next;
        }

        ListNode rightNode = beforeLeft;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        ListNode afterRight = rightNode.next;
        ListNode leftNode = beforeLeft.next;

        beforeLeft.next = null;
        rightNode.next = null;

        reverseList(leftNode);

        beforeLeft.next = rightNode;
        leftNode.next=afterRight;
        return temp.next;



    }

    public void reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        ListNode cur = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

    }

}
